/*
 * @ProjectName: 编程学习
 * @Copyright:   2021 HangZhou Yiyuery Dev, Ltd. All Right Reserved.
 * @address:     微信搜索公众号「架构探险之道」获取更多资源。
 * @date:        2021/1/5 10:09 上午
 * @blog:         https://yiyuery.blog.csdn.net/
 * @description: 本内容仅限于编程技术学习使用，转发请注明出处.
 */
package pub.dsb.example.algorithm;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * <p>
 * https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
 * </p>
 *
 * @author Yi
 * @date 2021/1/5 10:09 上午
 * @sine 1.0
 */
public class LC4Test {
    public static void main(String[] args) {
        //2,3,3 ,4,4, 5,5,7
//        System.out.println("\n"+new Solution20200105().findMedianSortedArrays(new int[]{2, 3, 4, 5}, new int[]{3, 4, 5, 7}));
//        System.out.println("\n"+new Solution20200105().findMedianSortedArrays(new int[]{1, 2}, new int[]{3, 4}));
        System.out.println("\n"+new Solution20200105().findMedianSortedArrays(new int[]{1, 3}, new int[]{2}));
    }
}

class Solution20200105 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        /*
        [x,x,x,x,x,x] 从小到大
        [y,y,y,y,y,y,y,y,y,y] 从小到大
         */
        List<Integer> values = new ArrayList<>();
        int pos = 0;
        for (int i = 0; i < nums1.length; i++) {
            int v1 = nums1[i];
            while (nums2.length > pos && nums2[pos] <= v1) {
                values.add(nums2[pos++]);
            }
            values.add(v1);
        }
        if (pos < nums2.length) {
            for (int i = pos; i < nums2.length; i++) {
                values.add(nums2[pos++]);
            }
        }
        values.forEach(p -> System.out.print((int)p));
        return values.size() % 2 == 0 ? (values.get(values.size() / 2 - 1) + values.get(values.size() / 2)) / 2.0
                : values.get(values.size() / 2);
    }
}
